<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="umsroot.css">
<TITLE>
Details of the Execution Mechanism
</TITLE>
</HEAD>
<BODY >
<A HREF="umsroot114.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="umsroot104.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="umsroot116.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc256">17.11</A>&nbsp;&nbsp;Details of the Execution Mechanism</H2><UL>
<LI><A HREF="umsroot115.html#toc143">Particularities of Waking by Unification</A>
<LI><A HREF="umsroot115.html#toc144">Cuts and Suspended Goals</A>
</UL>


<A NAME="toc143"></A>
<H3 CLASS="subsection"><A NAME="htoc257">17.11.1</A>&nbsp;&nbsp;Particularities of Waking by Unification</H3>
<A NAME="@default1037"></A>
Goals that are suspended on the <B>inst</B> or <B>bound</B> waking
conditions are woken by unifications of their
<I>suspending variables</I>.
<A NAME="@default1038"></A>
One suspending variable can be responsible for delaying several goals,
on the other hand one goal can be suspended on several
suspending variables (as alternative waking conditions).
This means that when one suspending variable is bound,
several delayed goals may be woken at once.
The order of executing woken suspended goals does not necessarily correspond
to the order of their suspending. It is in fact determined by their
priorities and is implementation-dependent within the same priority group.<BR>
<BR>
The waking process never interrupts unifications and/or a sequence
of simple goals.
<A NAME="@default1039"></A>
Simple goals are a subset of the built-ins and
can be recognised by their <B>call_type</B>
flag as returned by
<A HREF="../bips/kernel/compiler/get_flag-3.html"><B>get_flag/3</B></A><A NAME="@default1040"></A>,
simple goals having the type <TT>external</TT>.
Note also that some predicates, e.g. <A HREF="../bips/kernel/arithmetic/is-2.html"><B>is/2</B></A><A NAME="@default1041"></A>,
are normally in-line expanded and thus simple, but can be regular when
inlining is suppressed, e.g. by the <B>pragma(noexpand)</B> directive.<BR>
<BR>
ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> treats simple predicates (including unification) always as a block.
Delayed goals are therefore woken only at the end of a successful
unification and/or a sequence of simple goals.
If a suspending variable is bound in a simple goal, the suspended
goals are woken only at the end of the last consecutive simple
goal or at the clause end.
If the clause contains simple goals at the beginning of its
body, they are considered part of the head (<I>extended head</I>)
<A NAME="@default1042"></A>
and if a suspending variable is bound in the head unification or
in a simple predicate in the extended head, the corresponding
delayed goals are woken at the end of the extended head.<BR>
<BR>
A
<A HREF="../bips/kernel/control/I-0.html"><B>cut</B></A><A NAME="@default1043"></A>
is also considered a simple goal and is therefore
always executed <B>before</B> waking any pending suspended goals.
This is important to know especially in the situations where the cut
acts like a guard, immediately after the clause neck or after
a sequence of simple goals.
If the goals woken by the head unification or by the extended head
are considered as constraints on the suspending variables,
the procedure will not behave as expected.
For example
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
filter(_P,[],[]) :- !.
filter(P,[N|LI],[N|NLI]) :-
        N mod P =\= 0,
        !,
        filter(P,LI,NLI).
filter(P,[N|LI],NLI) :-
        filter(P,LI,NLI).

delay integers(_, List) if var(List).
integers(_, []).
integers(N, [N|Rest]) :-
        N1 is N + 1,
        integers(N1, Rest).
 
?- integers(2, Ints), filter(2, Ints, [X1,X2]).
</PRE></BLOCKQUOTE>
The idea here is that integers/2 fills a list with integers on demand,
i.e. whenever new list elements appear.
Filter/3 is a predicate that removes all integers that are a multiple
of P. In the example query, the call to <B>integers/2</B> initially delays.
When <B>filter/3</B> is called, Ints gets instantiated in the head unification
of the second clause of filter/3, which will wake up integers/2. However,
since the second clause of filter/3 has an extended head which extends up to
the cut, integers/2 will not actually be executed until after the cut.
Therefore, N is not yet instantiated at the time of the arithmetic test
and causes an error message.<BR>
<BR>
The reason why delayed goals are woken <B>after</B> the cut and not before
it is that neither of the two possibilities is always the intended
or the correct one, however when goals are woken <B>before</B> the cut,
there is no way to escape it and wake them after, and so if
a nondeterministic goal is woken, it is committed by this cut
which was most probably not intended.
On the other hand, it is always possible to force waking before the cut
by inserting a regular goal before it, for example <A HREF="../bips/kernel/control/true-0.html"><B>true/0</B></A><A NAME="@default1044"></A>,
so the sequence
<DIV CLASS="center">
<B>true, !</B>
</DIV>
can be viewed as a special cut type.<BR>
<BR>
As a consequence, the example can be fixed by inserting <TT>true</TT> at the
beginning of the second clause.
However, a preferable and more robust way is using the if-then-else
construct, which always forces waking suspended goals before
executing the condition.
This would also be more efficient by avoiding the creation of a choice point:
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
filter(_P,[],[]).
filter(P,[N|LI],LL) :-
        (N mod P =\= 0 -&gt;
                LL = [N|NLI],
                filter(P, LI, NLI)
        ;
                filter(P,LI,LL)
        ).
</PRE></BLOCKQUOTE>
<A NAME="toc144"></A>
<H3 CLASS="subsection"><A NAME="htoc258">17.11.2</A>&nbsp;&nbsp;Cuts and Suspended Goals</H3>
<A NAME="delaycut"></A>The
<A HREF="../bips/kernel/control/I-0.html"><B>cut</B></A><A NAME="@default1045"></A>
relies on a fixed order of goal execution in that it discards
some choice points if all goals preceding it in the clause body have
succeeded.
If some of these goals delay without being woken before the cut,
or if the head unification of the
clause with the cut wakes any nondeterministic delayed goal,
the completeness of the resulting program is lost
and there is no clean way to save it as long as the cut is used.
<BR>
<BR>
<A NAME="@default1046"></A>
The user is strongly discouraged to use non-local cuts together with
coroutining, or to be precisely aware of their scope.
The danger of a cut is twofold:
<UL CLASS="itemize"><LI CLASS="li-itemize">
Delaying <B>out of</B> the scope of a cut:
a cut can be executed after some calls preceding it in the clause
(or children of these calls) delay. When they are then woken later,
they may cause the whole execution to fail instead of just the
guard before the cut.<BR>
<BR>
<LI CLASS="li-itemize">Delaying <B>into</B> the scope of a cut:
the head unification of a clause with cuts can wake delayed goals.
If they are nondeterministic, the cut in the body of the waking clause
will commit even the woken goals
</UL>
<HR>
<A HREF="umsroot114.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="umsroot104.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="umsroot116.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
